#ifndef GAMEENGINE_CORE_GRAPH_QUADTREE_NODE_H
#define GAMEENGINE_CORE_GRAPH_QUADTREE_NODE_H

#include <GameEngine/Core/core_settings.h>

#include <GameEngine/Geometry/Surfaces/box2d.h>

#include <list>
#include <vector>

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

template <class Q> class QuadtreeNodeIterator;
template <class Q> class QuadtreeNodeConstIterator;

//=====================================================================

namespace QuadtreeNodeItr {
	//! Enumerates the types of nodes on which it is possible to iterate in a quadtree
	enum QuadtreeNodeItrType {
		//! Iteration on all the nodes of the quadtree
		AllNodes,
		//! Iteration on the low-level nodes of the quadtree. Low-level nodes are nodes that do not have children
		LowLevelNodes,
		//! Iteration on the non-empty nodes of the quadtree
		NonEmptyNodes
	};
}

//=====================================================================

//! Class in charge of representing a node in a quad tree
/*!
 *  A node in a quadtree can recursively be subdivided into four subnodes. Each
 *  quadtree node can contain some elements.
 *
 *  A quadtree node is templated by two parameters: E represents the type of elements
 *  stored by the quadtree and T represents the level of numerical precision required
 *  for space subdivision (T would typically either be of type float or double).
 */
template <class E, class T>
class QuadtreeNode {

public:
	//! Typedef used to handle number of elements
	typedef unsigned int ElementCount;

	//! Typedef used to iterate through nodes
	typedef QuadtreeNodeIterator<QuadtreeNode> Iterator;
	//! Typedef used to iterate through constant nodes
	typedef QuadtreeNodeConstIterator<QuadtreeNode> IteratorConst;

public:
	QuadtreeNode();
	QuadtreeNode(const Box2d<T>& box);
	QuadtreeNode(const QuadtreeNode& rhs);
	~QuadtreeNode();
	QuadtreeNode& operator=(const QuadtreeNode& rhs);

	QuadtreeNode* children() const;
	const Box2d<T>& box() const;

	const std::vector<E>& elements() const;
	std::vector<E>& elements();

	bool subdivide();
	bool merge(bool unique = true);

	bool add_element(const E& element, const Point2d<T>& location, bool unique = true);
	bool add_element(const E& element, const Box2d<T>& location);
	ElementCount remove_element(const E& element, bool recursive = true);
	bool find_element(const E& element, bool recursive = true) const;

	ElementCount nb_elements(bool recursive = true) const;

	bool is_non_empty() const;
	bool is_low_level() const;

	const QuadtreeNode* get_node(const Point2d<T>& location) const;
	QuadtreeNode* get_node(const Point2d<T>& location);
	std::list< const QuadtreeNode* > get_nodes(const Box2d<T>& location,
		QuadtreeNodeItr::QuadtreeNodeItrType type = QuadtreeNodeItr::LowLevelNodes) const;
	std::list< QuadtreeNode* > get_nodes(const Box2d<T>& location,
		QuadtreeNodeItr::QuadtreeNodeItrType type = QuadtreeNodeItr::LowLevelNodes);

protected:
	//! Typedef used to handle QuadtreeNode pointers
	typedef QuadtreeNode* SelfPtr;
	//! Typedef used to handle QuadtreeNode constant pointers
	typedef const QuadtreeNode* SelfPtrConst;

protected:
	bool add_element(const E& element, bool unique = true, bool check_children = true);

	static bool get_nodes_recursive(const QuadtreeNode& node, std::list<SelfPtrConst>& list,
		const Box2d<T>& location, QuadtreeNodeItr::QuadtreeNodeItrType type);
	static bool get_nodes_recursive(QuadtreeNode& node, std::list<SelfPtr>& list,
		const Box2d<T>& location, QuadtreeNodeItr::QuadtreeNodeItrType type);

protected:
	//! Children nodes
	QuadtreeNode* children_;

	//! Valid box
	Box2d<T> box_;

	//! Elements
	std::vector<E> elements_;
};

//=====================================================================

//! Iterates through the children of a QuadtreeNode
/*!
 *  This iterator allows to iterate through the subnodes of a QuadtreeNode with three
 *  different manners: either iterate through all the nodes, all the low-level nodes
 *  (i.e., the nodes that do not have children) or all the non-empty nodes.
 *
 *  An example of such an iteration could be:
 *  @code
 *  QuadtreeNode<E,T> node = ...;
 *  
 *  for ( QuadtreeNode<E,T>::Iterator it(node); it.more(); it.next() ) {
 *		// Access current subnode
 *		QuadtreeNode<E,T>& current = it.cur();
 *  
 *		// do stuff...
 *  }
 *  @endcode
 *  Please note that in the example, the iterator is built as a QuadtreeNode<E,T>::Iterator
 *  object. This is a typedef provided in the QuadtreeNode class - in practice, this is strictly
 *  equivalent to QuadtreeNodeIterator< QuadtreeNode<E,T> > (although this is generally more
 *  convenient to type).
 *
 *  This class provides read-write access to the elements of the quadtree node. If
 *  you want read-only access, please use the QuadtreeNodeConstIterator class.
 *
 @note Any change in the QuadtreeNode object will invalidate all iterators using it. The
       behavior of the iterator is unpredictable in case of such a change.
 */
template <class Q>
class QuadtreeNodeIterator {

public:
	QuadtreeNodeIterator(Q& node, QuadtreeNodeItr::QuadtreeNodeItrType type = QuadtreeNodeItr::LowLevelNodes);
	~QuadtreeNodeIterator();

	bool more() const;
	void next();
	Q& cur();
	const Q& cur() const;

private:
	void push_node(Q& node);
	void pop_node();

	void pop_node_low_level();
	void pop_node_all();
	void pop_node_non_empty();

private:
	//! Function pointer typedef used to call the correct pop function
	typedef void (QuadtreeNodeIterator::*POP_FUNC)();

private:
	//! Pop function
	POP_FUNC pop_func_;

	//! The current node of the iterator
	Q* node_;

	//! The next node of the iterator
	Q* next_node_;

	//! List of nodes
	std::list< std::pair<Q*,int> > nodes_to_explore_;
};

//=====================================================================

//! Iterates through the children of a QuadtreeNode (constant iterator)
/*!
 *  This iterator allows to iterate through the subnodes of a QuadtreeNode with three
 *  different manners: either iterate through all the nodes, all the low-level nodes
 *  (i.e., the nodes that do not have children) or all the non-empty nodes.
 *
 *  An example of such an iteration could be:
 *  @code
 *  QuadtreeNode<E,T> node = ...;
 *  
 *  for ( QuadtreeNode<E,T>::IteratorConst it(node); it.more(); it.next() ) {
 *		// Access current subnode
 *		const QuadtreeNode<E,T>& current = it.cur();
 *  
 *		// do stuff...
 *  }
 *  @endcode
 *  Please note that in the example, the iterator is built as a QuadtreeNode<E,T>::IteratorConst
 *  object. This is a typedef provided in the QuadtreeNode class - in practice, this is strictly
 *  equivalent to QuadtreeNodeConstIterator< QuadtreeNode<E,T> > (although this is generally more
 *  convenient to type).
 *
 *  This class solely provides read-only access to the elements of the quadtree node. If
 *  you want read-write access, please use the QuadtreeNodeIterator class.
 *
 @note Any change in the QuadtreeNode object will invalidate all iterators using it. The
       behavior of the iterator is unpredictable in case of such a change.
 */
template <class Q>
class QuadtreeNodeConstIterator {

public:
	QuadtreeNodeConstIterator(const Q& node, QuadtreeNodeItr::QuadtreeNodeItrType type = QuadtreeNodeItr::LowLevelNodes);
	~QuadtreeNodeConstIterator();

	bool more() const;
	void next();
	const Q& cur();

private:
	void push_node(const Q& node);
	void pop_node();

	void pop_node_low_level();
	void pop_node_all();
	void pop_node_non_empty();

private:
	//! Function pointer typedef used to call the correct pop function
	typedef void (QuadtreeNodeConstIterator::*POP_FUNC)();

private:
	//! Pop function
	POP_FUNC pop_func_;

	//! The current node of the iterator
	const Q* node_;

	//! The next node of the iterator
	const Q* next_node_;

	//! List of nodes
	std::list< std::pair<const Q*,int> > nodes_to_explore_;
};

//=====================================================================

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#include <GameEngine/Core/Graph/quadtree_node.hpp>

#endif
